home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Crafty-15.19.lha / crafty-15.19 / src / thread.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  13KB  |  306 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* modified 04/28/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Thread() is the driver for the threaded parallel search in Crafty.  the    *
  13. *   basic idea is that whenever we notice that one (or more) threads are       *
  14. *   in their idle loop, we drop into thread, from Search(), and begin a new    *
  15. *   parallel search from this node.  this is simply a problem of copying the   *
  16. *   search state space for each thread working at this node, then sending      *
  17. *   everyone off to SearchSMP() to search this node in parallel.               *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. #if defined(SMP)
  22. int Thread(TREE *tree) {
  23.   TREE *block;
  24.   int proc;
  25.   int nblocks=0;
  26. /*
  27.  ----------------------------------------------------------
  28. |                                                          |
  29. |   first, we make sure that there are idle threads. it    |
  30. |   is possible that we get here after they have all been  |
  31. |   claimed by another thread.  in that case we return.    |
  32. |                                                          |
  33.  ----------------------------------------------------------
  34. */
  35.   Lock(lock_smp);
  36.   for (proc=0;proc<max_threads && thread[proc];proc++);
  37.   if (proc == max_threads || tree->stop) {
  38.     UnLock(lock_smp);
  39.     return(0);
  40.   }
  41. # if defined(DEBUGSMP)
  42.   Lock(lock_io);
  43.   Print(128,"thread %d  block %d  ply %d  parallel split\n",
  44.         tree->thread_id,FindBlockID(tree),tree->ply);
  45.   Print(128,"thread %d  threads(s) idle:",tree->thread_id);
  46.   for (proc=0;proc<max_threads;proc++) 
  47.     if (!thread[proc]) Print(128," %d",proc);
  48.   Print(128,"\n");
  49.   UnLock(lock_io);
  50. #endif
  51. /*
  52.  ----------------------------------------------------------
  53. |                                                          |
  54. |   now we start copying the current "state" from this     |
  55. |   thread into new thread blocks so that the threads can  |
  56. |   search this position without interfering with each     |
  57. |   other.  as we copy, we link those blocks as siblings   |
  58. |   of the parent node, and point each sibling back to the |
  59. |   parent so we can unwind this confusion as the threads  |
  60. |   complete their work.                                   |
  61. |                                                          |
  62.  ----------------------------------------------------------
  63. */
  64.   thread[tree->thread_id]=0;
  65.   tree->nprocs=0;
  66.   tree->done=0;
  67.   for (proc=0;proc<max_threads;proc++) {
  68.     tree->siblings[proc]=0;
  69.     if (thread[proc] == 0) {
  70.       block=CopyToSMP(tree);
  71.       if (!block) continue;
  72.       nblocks++;
  73.       tree->siblings[proc]=block;
  74.       block->thread_id=proc;
  75.       block->parent=tree;
  76.       tree->nprocs++;
  77. #if defined(DEBUGSMP)
  78.       Print(128,"thread %d  block %d  allocated at ply=%d\n",
  79.             proc,FindBlockID(block),tree->ply);
  80. #endif
  81.     }
  82.     else tree->siblings[proc]=0;
  83.   }
  84.   tree->search_value=tree->value;
  85.   if (!nblocks) {
  86.     UnLock(lock_smp);
  87.     thread[tree->thread_id]=tree;
  88.     return(0);
  89.   }
  90. /*
  91.  ----------------------------------------------------------
  92. |                                                          |
  93. |   everything is set.  now we can stuff the address of    |
  94. |   the thread blocks into thread[i] so that those idle    |
  95. |   threads can begin the parallel search.                 |
  96. |                                                          |
  97.  ----------------------------------------------------------
  98. */
  99.   for (proc=0;proc<max_threads;proc++)
  100.     if (tree->siblings[proc])
  101.       thread[proc]=tree->siblings[proc];
  102. /*
  103.  ----------------------------------------------------------
  104. |                                                          |
  105. |   after the threads are kicked off to start the parallel |
  106. |   search using the idle threads, this thread has to be   |
  107. |   inserted as well.  however, since it is possible that  |
  108. |   this thread may finish before any or all of the other  |
  109. |   parallel threads, this thread is sent to ThreadWait()  |
  110. |   which will immediately send it to SearchSMP() just     |
  111. |   like the other threads.  going to ThreadWait() allows  |
  112. |   this thread to join others if it runs out of work to   |
  113. |   do.  we do pass ThreadWait() the address of the parent |
  114. |   thread block, so that if this thread becomes idle, and |
  115. |   this thread block shows no threads are still busy,     |
  116. |   then this thread can return to here and then back up   |
  117. |   into the previous ply as it should.  note that no      |
  118. |   other thread can back up to the previous ply since     |
  119. |   their recursive call stacks are not set for that.      |
  120. |                                                          |
  121.  ----------------------------------------------------------
  122. */
  123.   UnLock(lock_smp);
  124.   ThreadWait(tree->thread_id, tree);
  125. # if defined(DEBUGSMP)
  126.   Print(128,"thread %d  block %d  ply %d  parallel join\n",
  127.         tree->thread_id,FindBlockID(tree), tree->ply);
  128. #endif
  129.   return(1);
  130. }
  131.  
  132. /* modified 04/09/98 */
  133. /*
  134. ********************************************************************************
  135. *                                                                              *
  136. *   ThreadInit() is called from the pthread_create() function.  it then calls  *
  137. *   ThreadWait() with the appropriate arguments to park the new threads until  *
  138. *   work is available.                                                         *
  139. *                                                                              *
  140. ********************************************************************************
  141. */
  142. void *ThreadInit(void *tid) {
  143.   ThreadWait((int) tid, (TREE*) 0);
  144.   return(0);
  145. }
  146.  
  147. /* modified 04/26/98 */
  148. /*
  149. ********************************************************************************
  150. *                                                                              *
  151. *   ThreadStop() is called from SearchSMP() when it detects a beta cutoff (or  *
  152. *   fail high) at a node that is being searched in parallel.  we need to stop  *
  153. *   all threads here, and since this threading algorithm is "recursive" it may *
  154. *   be necessary to stop other threads that are helping search this branch     *
  155. *   further down into the tree.  this function simply sets tree->stop to 1,    *
  156. *   which will stop that particular thread instantly and return it to the idle *
  157. *   loop in ThreadWait().                                                      *
  158. *                                                                              *
  159. ********************************************************************************
  160. */
  161. void ThreadStop(TREE *tree) {
  162.   int proc;
  163.   Lock(tree->lock);
  164.   tree->stop=1;
  165.   for (proc=0;proc<max_threads;proc++)
  166.     if (tree->siblings[proc]) ThreadStop(tree->siblings[proc]);
  167.   UnLock(tree->lock);
  168. #if defined(DEBUGSMP)
  169.   Lock(lock_io);
  170.   Print(128,"thread %d (block %d) being stopped by beta cutoff.\n",
  171.         tree->thread_id,FindBlockID(tree));
  172.   UnLock(lock_io);
  173. #endif
  174. }
  175.  
  176. /* modified 04/09/98 */
  177. /*
  178. ********************************************************************************
  179. *                                                                              *
  180. *   ThreadWait() is the idle loop for the N threads that are created at the    *
  181. *   beginning when Crafty searches.  threads are "parked" here waiting on a    *
  182. *   pointer to something they should search (a parameter block built in the    *
  183. *   function Thread() in this case.  when this pointer becomes non-zero, each  *
  184. *   thread "parked" here will immediately call SearchSMP() and begin the       *
  185. *   parallel search as directed.                                               *
  186. *                                                                              *
  187. ********************************************************************************
  188. */
  189. int ThreadWait(int tid, TREE *waiting) {
  190. /*
  191.  ----------------------------------------------------------
  192. |